package com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.algorithms.shortestpath;

import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Edge;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Graph;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Vertex;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.line.IndexPriorityQueue;
import lombok.Setter;
import lombok.experimental.Accessors;

import java.util.*;
import java.util.stream.Collectors;

/**
 * <h1>最短路径-Dijkstra算法<h1/>
 * <p>
 *     适用于有向有环图。
 * </p>
 * <p>
 *     思想：设置起点权重为0,其他顶点权重为正无穷。把起点的权重放入优先级队列，循环每次从优先级队列中获取权重最小的顶点，进行放松操作。直到优先级
 *     队列中没有数据。
 * </p>
 */
public class DijkstraSP<T> {
    @Setter
    @Accessors(chain = true)
    private Graph<T> graph;
    //链接定点的边
    private Map<Vertex<T>, Edge<T>> map;
    //到边的最近的权重
    private Map<Vertex<T>, Double> distTo;
    //定点的优先级队列
    private IndexPriorityQueue<Vertex<T>, Double> indexPriorityQueue;
    private Vertex<T> source;


    public double distTo(T target) {
        return distTo.get(Vertex.create(target));
    }

    public boolean hasPathTo(T target){
        return this.map.containsKey(Vertex.create(target));
    }

    public Iterable<Edge<T>> pathTo(T target){

        //路径

        Deque<Edge<T>> result = new LinkedList<>();

        for (Edge<T> edge = this.map.get(Vertex.create(target));edge!=null;edge=map.get(edge.getFrom())) {
            result.push(edge);
        }

        return result;
    }





    private DijkstraSP<T> init(){
        //初始化 设置所有的定点权重都是无穷
        this.graph.getVertices().entrySet().forEach(entity->{
            distTo.put(entity.getValue(), Double.MAX_VALUE);
        });
        //从起点开始
        distTo.put(source, 0.0d);
        indexPriorityQueue.insert(source,0.0d);
        //每次都找到路径最短的一个顶点。如果出发relax操作，会有新的顶点加入到里面。
        while(!indexPriorityQueue.isEmpty()){
            relax(indexPriorityQueue.pull().getKey());
        }
        return this;
    }


    /**
     * 进行最短路径的relax方法。判断当前边是不是目标顶点的最短路径。
     * @param vertex
     */
    private void relax(Vertex<T> vertex){
        //遍历顶点
        vertex.getNext().forEach(edge->{

            Vertex<T> to = edge.getTo();
            //判断经过当前边的权重是不是比之前的要短。
            if(distTo.get(to)>distTo.get(vertex)+edge.getWeight()){
                distTo.put(to, distTo.get(vertex)+edge.getWeight());
                if(indexPriorityQueue.contains(to)){
                    indexPriorityQueue.change(to,distTo.get(to));
                }else {
                    indexPriorityQueue.insert(to,distTo.get(to));
                }
                this.map.put(to, edge);
            }

        });

    }


    private DijkstraSP(Graph<T> graph,T source){
        this.graph = graph;
        this.source = graph.getVertices().get(Vertex.create(source));
        this.map = new HashMap<>(graph.getVertices().keySet().size());
        this.indexPriorityQueue = new IndexPriorityQueue<>(graph.getVertices().keySet().size(), true);
        this.distTo = new HashMap<>(graph.getVertices().keySet().size());

    }

    public static <T> DijkstraSP<T> create(Graph<T> graph,T source){
        return new DijkstraSP<>(graph,source).init();
    }

}
